//题目:
// 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
// 一个字符串的 子序列 是指这样一个新的字符串：
// 它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
// 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
// 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int longestCommonSubsequence(string text1, string text2) 
    {
        string s1=" "+text1,s2=" "+text2;
        //1.创建dp表————dp[i][j]表示:s1中[0,i]区间和s2中[0,j]区间，所有子序列中，最长公共子序列的长度
        vector<vector<int>> dp(s1.size(),vector<int>(s2.size()));
        //2.初始化 ———— 虚拟行、列
        //3.填表 ———— 从上玩下 + 从左往右
        for(int i=1;i<s1.size();i++)
        {
            for(int j=1;j<s2.size();j++)
            {
                if(s1[i]==s2[j]) 
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
            }
        }
        //4.确定返回值
        return dp[s1.size()-1][s2.size()-1];
    }
};